package SwordFingerOffer;

import java.util.Arrays;

public class Q03_RepeatNumber {


    // O(NlogN)
    public static int findRepeatNumber_1(int[] nums) {
        Arrays.sort(nums);
        for (int j = 0; j < nums.length; j++) {
            if (nums[j + 1] == nums[j]){
                return nums[j + 1];
            }
        }
        return 0;
    }

    //O(N)
    public static int findRepeatNumber_2(int[] nums) {

        for (int i = 0; i < nums.length; i++) {
            while (i != nums[i]){
                if (!swap(nums,i,nums[i])){
                    return nums[i];
                }
            }
        }
        return 0;
    }

    private static boolean swap(int[] nums, int i, int j) {
        if (nums[i] == nums[j]){
            return false;
        }
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
        return true;
    }


    public static void main(String[] args) {
        findRepeatNumber_2(new int[]{2,3,1,0,2,5,3});
    }

}
